package sort;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/18 9:26
 * @Description
 */
public class Leet350 {
    public static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计较小的数组中元素出现的次数
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        //遍历较大的数组
        for (int num : nums2) {
            //判断元素在较小数组中出现的次数
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    //将次数-1，方便下次遍历
                    map.put(num, count);
                } else {
                    //如果没有该元素了，就将元素删除
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }

    public static void main(String[] args) {
        int[] nums1 = {4,9,5};
        int[] nums2 = {9,4,9,8,4};
        for (int i : intersect(nums1, nums2)) {
            System.out.println(i);
        }
    }

}
